package com.batunite.livedatabinding.views

import java.util.Collections
import java.util.LinkedList
import java.util.Queue

/**
 * author : r
 * time   : 2023/9/1 9:51 AM
 * desc   : 路径搜索工具类 from chatgpt
 */
class SearchPathHelper {
    companion object {

        /**
         * 寻径
         */
        fun findPath(
            maze: Array<IntArray>,
            start: IntArray,
            target: IntArray
        ): List<IntArray>? {
            val directions = arrayOf(
                intArrayOf(-1, 0),
                intArrayOf(1, 0),
                intArrayOf(0, -1),
                intArrayOf(0, 1)
            ) // 上下左右四个方向的偏移量
            val rows = maze.size
            val cols = maze[0].size
            val queue: Queue<IntArray> = LinkedList()
            val visited = Array(rows) {
                BooleanArray(
                    cols
                )
            }
            val parentMap = Array(rows) {
                Array(cols) {
                    IntArray(2)
                }
            }
            queue.offer(start)
            visited[start[0]][start[1]] = true
            while (!queue.isEmpty()) {
                val current = queue.poll()
                val x = current[0]
                val y = current[1]
                if (x == target[0] && y == target[1]) {
                    return reconstructPath(start, target, parentMap)
                }
                for (direction in directions) {
                    val newX = x + direction[0]
                    val newY = y + direction[1]
                    if (isValidMove(maze, visited, newX, newY)) {
                        queue.offer(intArrayOf(newX, newY))
                        visited[newX][newY] = true
                        parentMap[newX][newY] = intArrayOf(x, y)
                    }
                }
            }
            return null // 无法找到路径
        }

        /**
         * 是否可以到达
         */
        fun isValidMove(
            maze: Array<IntArray>,
            visited: Array<BooleanArray>,
            x: Int,
            y: Int
        ): Boolean {
            val rows = maze.size
            val cols = maze[0].size
            if (x < 0 || x >= rows || y < 0 || y >= cols) {
                return false // 超出边界
            }
            return !(visited[x][y] || maze[x][y] == GameView.WALL
                    || maze[x][y] == GameView.BOX_FILL || maze[x][y] == GameView.BOX_NOT)
        }

        /**
         * 重建路径
         */
        fun reconstructPath(
            start: IntArray,
            target: IntArray,
            parentMap: Array<Array<IntArray>>
        ): List<IntArray>? {
            val path: MutableList<IntArray> = ArrayList()
            var currentX = target[0]
            var currentY = target[1]
            while (currentX != start[0] || currentY != start[1]) {
                path.add(intArrayOf(currentX, currentY))
                val parent = parentMap[currentX][currentY]
                currentX = parent[0]
                currentY = parent[1]
            }
            path.add(intArrayOf(start[0], start[1]))
            Collections.reverse(path)
            return path
        }

        fun convertToDirections(path: List<IntArray>): List<Int>? {
            val directions: MutableList<Int> = ArrayList()
            for (i in 0 until path.size - 1) {
                val current = path[i]
                val next = path[i + 1]
                val dx = next[0] - current[0]
                val dy = next[1] - current[1]
                if (dx == -1 && dy == 0) {
                    directions.add(GameView.MOVE_TO_UP) // 上
                } else if (dx == 1 && dy == 0) {
                    directions.add(GameView.MOVE_TO_DOWN) // 下
                } else if (dx == 0 && dy == -1) {
                    directions.add(GameView.MOVE_TO_LEFT) // 左
                } else if (dx == 0 && dy == 1) {
                    directions.add(GameView.MOVE_TO_RIGHT) // 右
                }
            }
            return directions
        }

    }
}